#include <stdlib.h>
#include <ctime>
#include <climits>
#include <stdexcept>
#include <sstream>
#include "MyersAlgorythm.h"
#include "ReadAndPrint.h"
#include "Tests.h"



const int MAXN = INT_MAX / (1024 * 1024 * 8);
const int WORDS_AMOUNT_MAXN = INT_MAX / (1024 * 1024 * 2);
const int LINE_LENGTH_MAXN = INT_MAX / (1024 * 1024 * 4);

template<class iterator>
int StupidFindDistanceBetweenSequences(const Sequence<iterator>& first_sequence, 
						const Sequence<iterator>& second_sequence) {

    int first_sequence_length = first_sequence.GetLength();
    int second_sequence_length = second_sequence.GetLength();
   
    std::vector< std::vector<int> > answer(first_sequence_length + 1, std::vector<int>(second_sequence_length + 1));

    for (int i = 0; i <= first_sequence_length; ++i) {
        for (int j = 0; j <= second_sequence_length; ++j) {
	    if (i == 0 || j == 0) {
                answer[i][j] = 0;
		continue;
            } 
                
	    if (*(first_sequence.GetBegin() + i - 1) == *(second_sequence.GetBegin() + j - 1)) {
		answer[i][j] = answer[i - 1][ j - 1] + 1;
	    } else {
		answer[i][j] = 0;
		
	    }
	    answer[i][j] = std::max(answer[i - 1][j], std::max(answer[i][j], answer[i][j - 1]));
	         
        } 

    } 
  
    return (second_sequence_length - answer[first_sequence_length][second_sequence_length]) + 
		(first_sequence_length - answer[first_sequence_length][second_sequence_length]);
 }



void TestMaxCommonPrefix() {

    const auto max_common_prefix = [] (const std::string& first, const std::string& second) -> int {
    	return (MaxCommonPrefix(Sequence<std::string :: const_iterator>(first.begin(), first.end()),
			Sequence<std::string :: const_iterator>(second.begin(), second.end())));
    };

    if (max_common_prefix("abc", "cde") != 0 ||
        max_common_prefix("abracadabra", "abacaba") != 2 ||
	max_common_prefix("abbca", "abbac") != 3 ||
	max_common_prefix("ab", "ba") != 0 ||
        max_common_prefix("xxz", "xxx") != 2) throw std::logic_error("TestMaxCommonPrefix : FAIL");
    
}


template <class iterator>
void TestOneIterationOfAlgorythm(const Sequence<iterator>& first_sequence, 
		const Sequence<iterator>& second_sequence) {

    int first_sequence_length = first_sequence.GetLength();
    int second_sequence_length = second_sequence.GetLength();
    
    Massiv diag_checker(second_sequence_length, first_sequence_length);
    diag_checker[0] = MaxCommonPrefix(first_sequence, second_sequence);

    int distance_between_sequences = FindDistanceBetweenSequences(first_sequence, second_sequence);

    int left_border = std::min(distance_between_sequences, second_sequence_length);
    if (left_border % 2 != distance_between_sequences % 2) left_border--;
    int right_border = std::min(distance_between_sequences, first_sequence_length);
    if (right_border % 2 != distance_between_sequences % 2) right_border--;

    for (int i = 0; i < std::min(second_sequence_length, first_sequence_length); ++i) {
        OneIterationOfAlgorythm(first_sequence, second_sequence, &diag_checker, i);
	for (int diag_number = -left_border; diag_number <= right_border; diag_number += 2) {
	    Sequence<iterator> first_checking_sequence(first_sequence.GetBegin(), 
			first_sequence.GetBegin() + diag_checker[diag_number]);
	    Sequence<iterator> second_checking_sequence(second_sequence.GetBegin(), 
			second_sequence.GetBegin() + diag_checker[diag_number] - diag_number);
	    
	    if (StupidFindDistanceBetweenSequences(first_checking_sequence, second_checking_sequence) != i)
		throw std::logic_error("TestOneIterationOfAlgorythm : FAIL");
	}
    }
}


template <class iterator>
void TestFindDistanceBetweenSequences(const Sequence<iterator>& first_sequence, 
		const Sequence<iterator>& second_sequence) {

    if (FindDistanceBetweenSequences(first_sequence, second_sequence) != 
            StupidFindDistanceBetweenSequences(first_sequence, second_sequence))
        throw std::logic_error("TestFindDistanceBetweenSequences: FAIL");  
}

template <class iterator>
void TestFindOverlapPoint(const Sequence<iterator>& first_sequence, 
		const Sequence<iterator>& second_sequence) {

    
    int distance_between_sequences = FindDistanceBetweenSequences(first_sequence, second_sequence);

    iterator first_begin = first_sequence.GetBegin();
    iterator second_begin = second_sequence.GetBegin();
    iterator first_end = first_sequence.GetEnd();
    iterator second_end = second_sequence.GetEnd();
    
    Point point = FindOverlapPoint(distance_between_sequences, first_sequence, second_sequence);

    Sequence<iterator> left_first_sequence(first_begin, first_begin + point.x_); 
    Sequence<iterator> left_second_sequence(second_begin, second_begin + point.y_);

    Sequence<iterator> right_first_sequence(first_begin + point.x_, first_end); 
    Sequence<iterator> right_second_sequence(second_begin + point.y_, second_end);
    
    int distance_left = FindDistanceBetweenSequences(left_first_sequence, left_second_sequence);
    
    int distance_right = FindDistanceBetweenSequences(right_first_sequence, right_second_sequence);
    
    int distance_full = FindDistanceBetweenSequences(first_sequence, second_sequence);
    
    if ( !(distance_full == distance_left + distance_right && distance_left - distance_right <= 1 
            && distance_left - distance_right >= -1) ) 
        throw std::logic_error("TestFindOverlapPoint: FAIL");
    
}


void CheckAlgoAnswer(const std::vector<std::string>& first_sequence_strings, 
		const std::vector<std::string>& second_sequence_strings, std::stringstream& algo_answer) {

    
    std::string answer_line;
    int pointer_first_sequence_strings = 0;
    int pointer_second_sequence_strings = 0;
    int changes_amount_in_algo_answer = 0;

    Sequence<std::vector<std::string> :: const_iterator> first_sequence(first_sequence_strings.begin(),
		 first_sequence_strings.end());
    Sequence<std::vector<std::string> :: const_iterator> second_sequence(second_sequence_strings.begin(),
		 second_sequence_strings.end());

    int distance_between_two_sequences = StupidFindDistanceBetweenSequences(first_sequence, second_sequence);
    
    while(std::getline(algo_answer, answer_line)) {  
        
        if (answer_line[0] == do_nothing) {
            
            if (pointer_first_sequence_strings >= first_sequence_strings.size() || 
			pointer_second_sequence_strings >= second_sequence_strings.size()) 
                throw std::logic_error("TestEditScript: WRONG_LINE_NUMBER");
            
            
            if ((do_nothing + first_sequence_strings[pointer_first_sequence_strings]) != answer_line ||
		 	(do_nothing + second_sequence_strings[pointer_second_sequence_strings]) != answer_line)
                throw std::logic_error("TestEditScript: WRONG_SCRIPT");
            
            
            pointer_first_sequence_strings++;
            pointer_second_sequence_strings++;
        }
            
        if (answer_line[0] == add_string) {
            
            if (pointer_second_sequence_strings >= second_sequence_strings.size()) 
                throw std::logic_error("TestEditScript: WRONG_LINE_NUMBER");
            
            
            if ((add_string + second_sequence_strings[pointer_second_sequence_strings]) != answer_line) 
                throw std::logic_error("TestEditScript: WRONG_SCRIPT");
            
            
            pointer_second_sequence_strings++;
            changes_amount_in_algo_answer++;
        }
        
        if (answer_line[0] == delete_string) {
            
            if (pointer_first_sequence_strings > first_sequence_strings.size()) 
		throw std::logic_error("TestEditScript: WRONG_LINE_NUMBER");
 
            
            if ((delete_string + first_sequence_strings[pointer_first_sequence_strings]) != answer_line) 
                throw std::logic_error("TestEditScript: WRONG_SCRIPT");
            
            pointer_first_sequence_strings++;
            changes_amount_in_algo_answer++;
        }
            
    }
    
    if(changes_amount_in_algo_answer != distance_between_two_sequences) {
        throw std::logic_error("TestEditScript: WRONG_SCRIPT");
    }
    
}  


template <class iterator>
void GetCommonStringsNumbers(const std::vector<std::string>& first_sequence_strings, const std::vector<std::string>& second_sequence_strings, 
			const Sequence<iterator>& first_sequence, const Sequence<iterator>& second_sequence) {

    std::string algo_answer_string;

    std::stringstream algo_answer(algo_answer_string);

    std::vector<Point> common_strings_numbers = 
	GetCommonStringsNumbers(first_sequence_strings, second_sequence_strings);
	PrintSequenceOfChanges(first_sequence_strings, second_sequence_strings, 
		common_strings_numbers, algo_answer);
    
    CheckAlgoAnswer(first_sequence_strings, second_sequence_strings, algo_answer);

    algo_answer.clear();
}


std::vector<std::string> GenerateRandomSequence() {
    std::string string_template = "ABCDEFGHIGKLMNOPQRSTUVWXYZ";
  
    int words_amount = rand() % WORDS_AMOUNT_MAXN;

    std::vector<std::string> sequence_strings;
    std::string new_string_to_sequence;

    for (int i = 0; i < words_amount; ++i) { 
  
        int length_of_line = rand() % LINE_LENGTH_MAXN; 

        for (int j = 0; j < length_of_line ; ++j) {
	    new_string_to_sequence += string_template[rand() %26];
        } 
        sequence_strings.push_back(new_string_to_sequence);
    }
    return sequence_strings;
}


void Tests() {
    try {

	clock_t start;
        clock_t finish;

        std::cout << "Test : TestMaxCommonPrefix\n";
	start = clock();

	TestMaxCommonPrefix();

	finish = clock();
        std::cout << "-------------------------\nTotal work time is about " << (finish - start)
            << " ticks or " << (finish - start) / CLOCKS_PER_SEC << " seconds\n\n";

        for (int i = 0; i < MAXN; ++i) {

	    std::vector<std::string> first_sequence_string = GenerateRandomSequence();
	    std::vector<std::string> second_sequence_string = GenerateRandomSequence();

	    std::map<std::string, int> Map;
            std::vector<int> first_sequence_integrized = Integrize(first_sequence_string, &Map);
	    std::vector<int> second_sequence_integrized = Integrize(second_sequence_string, &Map);

	    Sequence<std::vector<int> :: iterator> first_sequence(first_sequence_integrized.begin(),
			 first_sequence_integrized.end());
	    Sequence<std::vector<int> :: iterator> second_sequence(second_sequence_integrized.begin(),
			 second_sequence_integrized.end());
		
	    std::cout << "Test : TestOneIterationOfAlgorythm\n";
            start = clock();

            TestOneIterationOfAlgorythm(first_sequence, second_sequence);

            finish = clock();
            std::cout << "-------------------------\nTotal work time is about " << (finish - start)
                << " ticks or " << (finish - start) / CLOCKS_PER_SEC << " seconds\n\n";


	    std::cout << "Test : TestFindDistanceBetweenSequences\n";
            start = clock();

            TestFindDistanceBetweenSequences(first_sequence, second_sequence);

            finish = clock();
            std::cout << "-------------------------\nTotal work time is about " << (finish - start)
                << " ticks or " << (finish - start) / CLOCKS_PER_SEC << " seconds\n\n";


	    std::cout << "Test : TestFindOverlapPoint\n";
            start = clock();
            TestFindOverlapPoint(first_sequence, second_sequence);

            finish = clock();
            std::cout << "-------------------------\nTotal work time is about " << (finish - start)
                << " ticks or " << (finish - start) / CLOCKS_PER_SEC << " seconds\n\n";


	    std::cout << "Test : GetCommonStringsNumbers\n";
            start = clock();

            GetCommonStringsNumbers(first_sequence_string, second_sequence_string, 
			first_sequence, second_sequence);

            finish = clock();
            std::cout << "-------------------------\nTotal work time is about " << (finish - start)
                << " ticks or " << (finish - start) / CLOCKS_PER_SEC << " seconds\n\n";
	    
	}        
    } catch (const std::exception& ex) {
        throw std::logic_error(std::string(ex.what()));
    }
}

int main() {
 Tests();
}



